package com.qisi.kandroidshalon.leetcode.partial;

import com.qisi.kandroidshalon.leetcode.Util;

/**
 * 分治思想
 */
public class Partial {
    /**
     * todo 归并排序、小和问题、逆序对
     */
    public static void mergeSort(Integer[] array) {
        if (array.length == 1) {
            return;
        }

        merge(array, 0, array.length - 1);

    }

    public static void merge(Integer[] array, int left, int right) {
        if (left == right) {
            return;
        }
        int mid = left + (right - left) / 2;
        //分治合并
        merge(array, left, mid);
        merge(array, mid + 1, right);
        mergeArray(array, left, mid, right);
        Util.dumpArray(array);
    }

    private static void mergeArray(Integer[] array, int left, int mid, int right) {
        int p1 = left;
        int p2 = mid + 1;
        Integer[] out = new Integer[right - left + 1];
        int i = 0;
        while (p1 <= mid && p2 <= right) {
            if (array[p1] < array[p2]) {
                out[i++] = array[p1++];
            } else {
                out[i++] = array[p2++];
            }
        }

        while (p1 <= mid) {
            out[i++] = array[p1++];
        }

        while (p2 <= right) {
            out[i++] = array[p2++];
        }

        for (int j = left; j <= right; j++) {
            array[j] = out[j - left];
        }
    }


    /**
     * todo 归并排序、小和问题、逆序对
     * <p>
     * 在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。
     * 1左边比1小的数，没有；
     * 3左边比3小的数，1；
     * 4左边比4小的数，1、3；
     * 2左边比2小的数，1；
     * 5左边比5小的数，1、3、4、2；
     * 所以小和为1+1+3+1+1+3+4+2=16
     * <p>
     * <p>
     * 思路,逆向思维：给定一个元素，只要它右边有比它大的元素，结果就会+1.利用二分思想，针对两个排好序的数组，只要右侧的比左侧的大就可以做累加
     */
    public static int smallSum(Integer[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        return mergeSortSum(arr, 0, arr.length - 1);
    }

    private static int mergeSortSum(Integer[] arr, int left, int right) {
        if (left == right) {
            return 0;
        }
        int mid = left + (right - left) / 2;
        return mergeSortSum(arr, left, mid) + mergeSortSum(arr, mid + 1, right) + mergeResult(arr, left, mid, right);
    }

    /**
     * 做一次合并排序，并计算结果
     *
     * @param array
     * @param left
     * @param mid
     * @param right
     * @return
     */
    private static int mergeResult(Integer[] array, int left, int mid, int right) {
        int result = 0;
        int p1 = left;
        int p2 = mid + 1;
        Integer[] out = new Integer[right - left + 1];
        int i = 0;
        while (p1 <= mid && p2 <= right) {
            //左边的小，则需要把左边的元素累加,累加次数为右侧指针右边的元素个数。累加完左边移动
            if (array[p1] < array[p2]) {
                result += (right - p2 + 1) * array[p1];
                out[i++] = array[p1++];
            } else {//右边的小，则不做累加，右指针移动,相等的时候也是右边移动，避免遗漏累加左边的
                out[i++] = array[p2++];
            }
        }
        //左边没遍历完,右边没有了，没有累加
        while (p1 <= mid) {
            out[i++] = array[p1++];
        }
        //右边的没遍历完，左边已经遍历完了，没有累加
        while (p2 <= right) {
            out[i++] = array[p2++];
        }

        for (int j = left; j <= right; j++) {
            array[j] = out[j - left];
        }
        return result;
    }

    public static void quickSort(Integer[] array) {
//        quickSortV1(array, 0, array.length - 1);
        quickSortV2(array, 0, array.length - 1);
    }

    private static void quickSortV1(Integer[] array, int left, int right) {
        //边界
        if (left >= right) {
            return;
        }
        int p = partialArray(array, left, right);
        quickSortV1(array, left, p - 1);
        quickSortV1(array, p + 1, right);
    }


    private static void quickSortV2(Integer[] array, int left, int right) {
//        边界
        if (left >= right) {
            return;
        }//如果某区域内都是连续相同的数，则返回边界会在[left,right]之外，递归调用会截止
        int[] p = partialArray2(array, left, right);
        quickSortV2(array, left, p[0]);
        quickSortV2(array, p[1], right);
    }

    /**
     * 在范围【left, right】内，按照数target划分左右两半，返回边界的索引
     * 思路 结合快慢指针，partial是左半区的边界,scanIndex往右边遍历
     * 1.如果【scanIndex】比target小，则和半区的下一个元素交换,半区向右边扩一位
     * 2.如果【scanIndex】比target大，则scanIndex往前走
     *
     * @param array
     * @param left
     * @param right
     * @return
     */
    public static int partialArray(Integer[] array, int left, int right) {
        if (left == right) {
            return right;
        }
        int target = array[right];
        int partial = left - 1;
        int scanIndex = left;
        while (scanIndex <= right) {
            if (array[scanIndex] <= target) {
                swap(array, partial + 1, scanIndex);
                partial++;
            }
            scanIndex++;
        }
        return partial;
    }


    /**
     * 荷兰国旗问题:两个指针记录左右边界L，R，一个指针扫scanIndex，边界移动时记录结果
     * 1.scanIndex较小，数向左侧交换，左边界移动，scanIndex移动
     * 2.scanIndex较大，数向右侧交换，有边界移动，scanIndex不动，因为交换过来的数还要比较
     * 3.相等，则两边不动，scanIndex移动
     * 4.循环直到scanIndex碰到右边界
     *
     * @param array
     * @param left
     * @param right
     * @return
     */
    public static int[] partialArray2(Integer[] array, int left, int right) {
        if (left == right) {
            return new int[]{left, right};
        }
        int[] result = new int[2];
        int target = array[right];
        int L = left - 1;
        int R = right + 1;
        //初始化
        result[0] = L;
        result[1] = R;
        int scanIndex = left;
        while (scanIndex < R) {//左右边界没有相遇
            if (array[scanIndex] < target) {//交换到左边，左边界前移
                swap(array, scanIndex++, ++L);
                result[0] = L;
            } else if (array[scanIndex] > target) {
                //和右边的交换，右边界左移,左边界不动，S也不动,记录右边界
                swap(array, scanIndex, --R);
                result[1] = R;
            } else {//相等则左指针前移,左右边界均不变
                scanIndex++;
            }
        }
        return result;
    }

    private static void swap(Integer[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }


}
